#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;
string LargestNum(vector<int>& nums) {
    // write code here
    if (nums.size() == 0)
    {
        return "";
    }
    if (nums.size() == 1)
    {
        return to_string(nums[0]);
    }
    vector<string> strNums(nums.size(), "");
    for (int i = 0; i < nums.size(); ++i)
    {
        strNums[i] = to_string(nums[i]);
    }
    sort(strNums.begin(), strNums.end(),greater<string>());
    string ans;
    for (int i=0;i< strNums.size();++i)
    {
        ans += strNums[i];
    }
    return ans;
}
vector<int> solution(vector<int>& costs, int coins) {
    // write code here
    vector<vector<int>> help(costs.size()+1, vector<int>(coins + 1, 0));
    for (int i = 1; i <= costs.size(); ++i) {
        for (int j = coins; j > 0; --j) {
            if (j < costs[i-1]) {
                continue;
            }
            help[i][j] = max(help[i-1][j], help[i-1][j - costs[i-1]] + 1);
        }
    }
    vector<int> ans(help[costs.size()][coins], 0);
    for (int i= coins,j= costs.size(),index= ans.size()-1;i>0&& index>0;) {
        if (help[j][i] == help[j - 1][i]) {
            --j;
        }
        else {
            ans[index--] = costs[j - 1];
            i -= costs[j-1];
            --j;
        }
    }
    return ans;
}
char str[1024] = { 0 };
string ReverseString(string originStr) {
    // write code here
    istringstream ist(originStr);
    string ans;
    while (ist.getline(str, 1024, ' ')) {
        reverse(str, str + strlen(str));
        ans.append(str);
        ans.push_back(' ');
        memset(str, 0, sizeof(str));
    }
    ans.resize(ans.size() - 1);
    return ans;
}

int main() {
    vector<int> v{ 5,2,3 };
    auto s=solution(v,1);
}